def knapsack_greedy(items, max_slots):
    """
    贪心算法解决背包问题（只考虑格子约束，价值最大化）

    参数:
    items (list): 物品列表，每个物品是一个字典，包含:
                  - name: 物品名称
                  - value: 物品价值
                  - slots: 物品占用格子数
    max_slots (int): 背包最大格子数

    返回:
    tuple: (选中的物品列表, 总价值)
    """
    # 计算每个物品的单位格子价值
    for item in items:
        item['value_per_slot'] = item['value'] / item['slots']

    # 按单位格子价值降序排序
    sorted_items = sorted(items, key=lambda x: x['value_per_slot'], reverse=True)

    # 贪心选择物品
    selected_items = []
    current_slots = 0
    total_value = 0

    for item in sorted_items:
        # 检查是否满足格子约束
        if current_slots + item['slots'] <= max_slots:
            selected_items.append(item)
            current_slots += item['slots']
            total_value += item['value']

    return selected_items, total_value


# 示例使用：只考虑格子约束（鼠鼠版）
if __name__ == "__main__":
    # 定义物品列表（名称、价值、占用格子数）
    items = [
        {"name": "非洲之心", "value": 10000, "slots": 1},
        {"name": "金砖", "value": 280, "slots": 2},
        {"name": "手表", "value": 200, "slots": 1},
        {"name": "阿萨拉周刊", "value": 5, "slots": 4},
        {"name": "复苏呼吸机", "value": 8000, "slots": 9},
        {"name": "水泥", "value": 30, "slots": 6},
    ]

    # 背包容量：5个格子
    max_slots = 14

    # 运行贪心算法
    selected, total = knapsack_greedy(items, max_slots=max_slots)

    # 输出结果
    print(f"背包最大格子数: {max_slots}")
    print(f"总价值: {total}  K")
    print("带走的物品:")
    for item in selected:
        print(f"- {item['name']}: 价值 {item['value']} 元, 占用 {item['slots']} 格")
    print(f"剩余格子: {max_slots - sum(item['slots'] for item in selected)}")